#include "type.h"
#include "bTree.h"
#include <string.h>
#include <stdio.h>

bool btree_init (struct root_node *root, btree_cmp cmp,
		btree_alloc data_alloc, btree_free data_free, btree_equal equal)
{
	/* equal can be NULL */
	if (!root || !cmp || !data_alloc || !data_free)
		return false;

	root->cmp = cmp;
	root->data_alloc = data_alloc;
	root->data_free = data_free;
	root->deal_equal = equal;
	root->head = NULL;

	return true;
}

bool btree_insert (struct root_node *root, void *arg)
{
	i_int32_t ret;
	struct b_tree *temp;

	if (!arg)
		return false;

	/* The first data */
	if (!root->head)
	{
		root->head = memcalloc (1, sizeof(struct b_tree));
		if (!root->head)
			return false;

		root->head->data = (*root->data_alloc)(arg);
		return true;
	}

	temp = root->head;
	while (temp)
	{
		ret = (*root->cmp)(arg, temp->data, NULL);

		if (ret < 0)
		{
			if (!temp->l)
			{
				temp->l = memcalloc (1, sizeof(struct b_tree));
				if (!temp->l)
					return false;

				temp->l->data = (*root->data_alloc)(arg);
				break;
			}
			else
			{
				temp = temp->l;
			}
		}
		else if (ret > 0)
		{
			if (!temp->r)
			{
				temp->r = memcalloc (1, sizeof(struct b_tree));
				if (!temp->r)
					return false;

				temp->r->data = (*root->data_alloc)(arg);
				break;
			}
			else
			{
				temp = temp->r;
			}
		}
		else
		{
			if (root->deal_equal)
			{
				(*root->deal_equal)(temp->data);
			}
			break;
		}
	}

	return true;
}

void btree_delete (struct root_node *root, void *arg)
{
	i_int32_t ret;
	struct b_tree *temp, *temp_parent = NULL;
	bool left;

	if (!arg || !root->head)
		return;

	temp = root->head;
	while (temp)
	{
		ret = (*root->cmp)(arg, temp->data, NULL);

		if (ret < 0)
		{
			if (temp->l)
			{
				left = true;
				temp_parent = temp;
				temp = temp->l;
			}
			else
			{
				return;
			}
		}
		else if (ret > 0)
		{
			if (temp->r)
			{
				left = false;
				temp_parent = temp;
				temp = temp->r;
			}
			else
			{
				return;
			}
		}
		else
		{
			struct b_tree *child;
			struct b_tree **parent;

			if (temp_parent)
			{
				if (left)
					parent = &temp_parent->l;
				else
					parent = &temp_parent->r;
			}
			else
			{
				parent = &root->head;
			}

			if (temp->r)
			{
				*parent = temp->r;
				child = temp->r;
				while (child->l) child = child->l;
				child->l = temp->l;
			}
			else
			{
				*parent = temp->l;
			}
			
			(*root->data_free)(temp->data);
			memfree (temp);
			break;
		}
	}
}

static void btree_delete_node (struct b_tree *node, btree_free del)
{
	if (!node || !del)
		return;

	if (node->l)
		btree_delete_node (node->l, del);

	if (node->r)
		btree_delete_node (node->r, del);

	(*del)(node->data);
	memfree (node);
}

void btree_delete_tree (struct root_node *root)
{
	btree_delete_node (root->head, root->data_free);
	root->head = NULL;
}

bool btree_is_empty (struct root_node *root)
{
	if (root->head == NULL)
		return true;

	return false;
}

